﻿// 132. 分割回文串 II.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>


using namespace std;
/*
https://leetcode.cn/problems/palindrome-partitioning-ii/
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。

示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：
输入：s = "a"
输出：0

示例 3：
输入：s = "ab"
输出：1

提示：
1 <= s.length <= 2000
s 仅由小写英文字母组成
*/


class Solution {
public:
    vector<vector<int>> dp;

    void Check(const string& s) {
        for (int i = 0; i < s.size(); i++) {
            dp[i][i] = 1;
            if (i + 1 < s.size() && s[i] == s[i + 1]) {
                dp[i][i+1] = 1;
            }
        }

        for (int i = 0; i < s.size(); i++) {
            int j = i + 2;
            int k = i;
            while (k >= 0 && j < s.size()) {
                if (s[k] == s[j] && dp[k + 1][j - 1] == 1) dp[k][j] = 1;
                k--; j++;
            }

            j = i + 3;
            k = i;
            while (k >= 0 && j < s.size()) {
                if (s[k] == s[j] && dp[k + 1][j - 1] == 1) dp[k][j] = 1;
                k--; j++;
            }
        }
    }

    int minCut(string s) {
        int malSize = s.size() + 10;
        dp.resize(malSize, vector<int>(malSize,0));

        Check(s);
        
        vector<int> cnt(malSize,0x3f3f3f3f);
        cnt[0] = 0;
        
        for (int i = 1; i < s.size(); i++) {
            cnt[i] = cnt[i - 1] + 1;
            if (dp[0][i] == 1) {
                cnt[i] = 0;
            }
            for (int j = 1; j <= i; j++) {
                if (dp[j][i] == 1) {
                    cnt[i] = min(cnt[i], cnt[j-1] + 1);
                }
            }
        }

        return cnt[s.size() - 1];
    }
};


int main()
{
    Solution s;

    cout << s.minCut("aab");
}
 